package com.waiting.leetcode;


import java.util.HashMap;
import java.util.Map;

class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {
    }

    public Node(int _val, Node _next, Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

public class CopyListWithRandomPointer138 {

    public Node copyRandomList(Node head) {
        Map<Node, Node> helper = new HashMap<>();
        Node q = head;
        while (q != null) {
            helper.put(q, new Node(q.val, null, null));
            q = q.next;
        }
        q = head;
        while (q != null) {
            Node tmp = helper.get(q);
            tmp.next = helper.get(q.next);
            tmp.random = helper.get(q.random);
            q = q.next;
        }
        return helper.get(head);
    }

    /**
     * 修改了原来的的列表
     * @param head
     * @return
     */
//    public Node copyRandomList(Node head) {
//        if (head == null) {
//            return head;
//        }
//        Node q = head;
//        while (q != null) {
//            Node newNode = new Node(q.val, q.next, q.random);
//            q.next = newNode;
//            q = newNode.next;
//        }
//        q = head.next;
//        while (q != null) {
//            if (q.random != null) {
//                q.random = q.random.next;
//            }
//            if (q.next != null) {
//                Node nextQ = q.next.next;
//                q.next = q.next.next;
//                q = nextQ;
//            } else {
//                q = null;
//            }
//        }
//        return head.next;
//    }
}
